package code1.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class P417 {

    //思路：如果判断每个点是否能流入太平洋与大西洋，那么时间负责度有O^n4，肯定爆了
    //考虑逆流而上，从四个边界上的点出发，标记能到达的点，若既能从太平洋到达也能从大西洋达到，那么就把该点加入结果集
    List<List<Integer>> results=new ArrayList<>();
    int m,n;
    int[][] go={{1,0},{-1,0},{0,-1},{0,1}};
    boolean[][] st1=new boolean[210][210];
    boolean[][] st2=new boolean[210][210];


    //左上边界出发
    void dfs1(int x,int y,int[][] heights){
        for(int i=0;i<4;i++){
            int nextx=x+go[i][0];
            int nexty=y+go[i][1];
            if(nextx>=0 && nextx<m && nexty>=0 && nexty<n && heights[nextx][nexty]>=heights[x][y] && !st1[nextx][nexty]){
                st1[nextx][nexty]=true;
                dfs1(nextx,nexty,heights);
            }
        }
    }

    //右下边界出发
    void dfs2(int x,int y,int[][] heights){
        for(int i=0;i<4;i++){
            int nextx=x+go[i][0];
            int nexty=y+go[i][1];
            if(nextx>=0 && nextx<m && nexty>=0 && nexty<n && heights[nextx][nexty]>=heights[x][y] && !st2[nextx][nexty]){
                st2[nextx][nexty]=true;
                dfs2(nextx,nexty,heights);
            }
        }
    }

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        m=heights.length;
        n=heights[0].length;
        //从边界出发，搜索判断能否达到
        for(int i=0;i<m;i++){
            st1[i][0]=true;
            dfs1(i,0,heights);
            st2[i][n-1]=true;
            dfs2(i,n-1,heights);
        }
        for(int i=0;i<n;i++){
            st1[0][i]=true;
            dfs1(0,i,heights);
            st2[m-1][i]=true;
            dfs2(m-1,i,heights);
        }
        //若都能到达，则加入结果集
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(st1[i][j] && st2[i][j]){
                    List<Integer> result=new ArrayList<>();
                    result.add(i);
                    result.add(j);
                    results.add(result);
                }
            }
        }
        return results;
    }
}
